A mathematical investigation of games of “take-away”

AbstractLet T be the collection of n-tuples of nonnegative integers, and S⊂T. In a “take-away game of type S with initial position t”, two players, starting with an initial vector t∈T, alternately subtract elements of S, subject to the remainder being in T, with the winner being the first to arrive at the zero vector. (NIM is such a game, with S consisting of all positive integer multiples of the unit vectors). The elements of T, considered as initial positions, can be classified as theoretical wins, draws, or losses for the first player, decomposing T into three disjoint sets, W(S), D(S), and L(S), respectively. Basic relationships among these sets are derived, and applied to the study of specific take-away games. A simple criterion for draw-free games is given, and in the one-dimensional case, a nonlinear shift register can be used as a “digital computer” to determine the winning and losing positions. The possibility of extending this recursive analysis to the entire class of “progressive games” is discussed